// 颜色分类

package Leetcode;

class solution_075 {
    public void sortColors(int[] nums) {
        QuickSort(nums, 0, nums.length - 1);
    }

    // 快速排序
    void QuickSort(int A[], int low, int high) {
        if (low < high) {
            int pivot_pos = Partition(A, low, high);// 划分
            QuickSort(A, low, pivot_pos - 1);// 划分左部分
            QuickSort(A, pivot_pos + 1, high);// 划分右部分
        }
    }

    // 用第一个元素将待排序序列划分成左右两个部分
    int Partition(int A[], int low, int high) {
        int pivot = A[low]; // 选取第一个元素作为枢轴
        while (low < high) { // 当low=high时结束
            while (low < high && A[high] >= pivot)
                high--;// 寻找右部分第一个小于枢轴的值
            A[low] = A[high];
            while (low < high && A[low] <= pivot)
                low++;// 寻找左部分第一个大于枢轴的值
            A[high] = A[low];
        }
        A[low] = pivot;// 枢轴元素存放在最终位置，此时low=high
        return low;// 返回此时枢轴的位置
    }
}

public class Solution075 {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p2 = nums.length - 1;
        for (int i = 0; i <= p2; i++) {
            // while循环是保证i位置上被交换后依然为2的情况
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                p2--;
            }
            // 判断为0一定要在判断为2的后面，因为经过多次交换可能最终停留在i位置上的是0
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                p0++;
            }
        }
    }
}
